import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

class Solution {

    public int shortestPathAllKeys(String[] grid) {
        int totalKeys = 0;
        int startI = 0;
        int startJ = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length(); j++) {
                char c = grid[i].charAt(j);
                if (c == '@') {
                    startI = i;
                    startJ = j;
                }
                int diff = c - 'a';
                if (diff >= 0 && diff < 6) {
                    totalKeys |= (1 << diff);
                }
            }
        }
        Deque<Node> queue = new ArrayDeque<>();
        queue.addLast(new Node(startI, startJ, 0));
        Set<String> visited = new HashSet<>();
        visited.add(getMark(startI, startJ, 0));
        int level = 0;
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int ignored = 0; ignored < size; ignored++) {
                Node node = queue.pollFirst();
                for (int[] dir : dirs) {
                    int i = node.i + dir[0];
                    int j = node.j + dir[1];
                    if (i < 0 || i >= grid.length) {
                        continue;
                    }
                    if (j < 0 || j >= grid[i].length()) {
                        continue;
                    }
                    String mark = getMark(i, j, node.keys);
                    if (visited.contains(mark)) {
                        continue;
                    }
                    char c = grid[i].charAt(j);
                    if (c == '#') {
                        continue;
                    }
                    if (c == '.' || c == '@') {
                        visited.add(mark);
                        queue.addLast(new Node(i, j, node.keys));
                        continue;
                    }
                    int diff = c - 'a';
                    if (diff >= 0 && diff < 6) {
                        int newKeys = node.keys | (1 << diff);
                        if (newKeys == totalKeys) {
                            return 1 + level;
                        }
                        visited.add(getMark(i, j, newKeys));
                        queue.addLast(new Node(i, j, newKeys));
                        continue;
                    }
                    diff = c - 'A';
                    if (diff >= 0 && diff < 6) {
                        int s = 1 << diff;
                        if ((node.keys & s) == s) {
                            visited.add(mark);
                            queue.addLast(new Node(i, j, node.keys));
                        }
                    }

                }
            }
            level += 1;
        }

        return -1;
    }


    private String getMark(int i, int j, int keys) {
        return i + "-" + j + "-" + keys;
    }

    class Node {
        private final int i;

        private final int j;

        private final int keys;

        Node(int i, int j, int keys) {
            this.i = i;
            this.j = j;
            this.keys = keys;
        }
    }
}
